package Backtracking;

import java.util.*;

public class 重新安排行程 {
    /* 回溯 */
    /*Map<String, Map<String, Integer>> map = new HashMap<>();
    List<String> res = new ArrayList<>();
    int targetLen;

    public List<String> findItinerary(List<List<String>> tickets) {
        targetLen = tickets.size() + 1;
        for (List<String> ticket : tickets) {
            Map<String, Integer> toMap = map.getOrDefault(ticket.getFirst(), new TreeMap<>());
            toMap.put(ticket.get(1), toMap.getOrDefault(ticket.get(1), 0) + 1);
            map.put(ticket.getFirst(), toMap);
        }
        res.add("JFK");
        backTracking("JFK");
        return res;
    }

    private boolean backTracking(String from) {
        if (res.size() == targetLen) return true;
        if (map.containsKey(from)) {
            for (Map.Entry<String, Integer> to : map.get(from).entrySet()) {
                Integer count = to.getValue();
                if (count > 0) {
                    res.add(to.getKey());
                    to.setValue(count - 1);
                    if (backTracking(to.getKey())) return true;
                    res.removeLast();
                    to.setValue(count);
                }
            }
        }
        return false;
    }*/

    Map<String, PriorityQueue<String>> flights = new HashMap<>();
    List<String> route = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            flights.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            flights.get(ticket.get(0)).offer(ticket.get(1));
        }
        dfs("JFK");
        return route;
    }

    private void dfs(String from) {
        PriorityQueue<String> to = flights.get(from);
        while (to != null && !to.isEmpty()) dfs(to.poll());
        route.addFirst(from);
    }
}
